import java.util.ArrayList;
import java.util.Collections;


class ABTreeInnerNode extends ABTreeNode {

	static int a = 2;
	static int b = 5;
	ArrayList<ABTreeNode> children = new ArrayList<ABTreeNode>();

	ABTreeInnerNode(ABTreeInnerNode parent) {
		this.parent = parent;
	}

	/**
	 * Gibt das kleinsten Wert in diesem Knoten aus.
	 * @return Den kleinsten Wert in diesem Knoten.
	 */
	int getLowestKey() {
		return children.get(0).getLowestKey();
	}

	/**
	 * Ermittelt das Blatt in dem Baum mit diesem Wert.
	 * @param value Der Wert zu dem das Blatt gefunden werden soll.
	 * @return Das Blatt.
	 */
	ABTreeNode getTargetNode(int value) {
		int i;
		for (i = 1; i < children.size(); ++i) {
			ABTreeNode child = children.get(i);
			int childLowestKey = child.getLowestKey();
			if (value < childLowestKey)
				break;
		}
		ABTreeNode child = children.get(i - 1);
		return child;
	}

	/**
	 * Fügt ein neues Blatt mit dem übergebenen Wert dem aktuellen Knoten hinzu.
	 */
	void insert(int value) {
		ABTreeNode child = getTargetNode(value);
		child.insert(value);
		checkSize();
	}

	/**
	 * Entfernt ein Blatt mit dem aktuellen Wert aus dem Knoten.
	 */
	void remove(int value) {
		ABTreeNode child = getTargetNode(value);
		child.remove(value);
		checkSize();
	}

	/**
	 * Überprüft die Anzahl der Kinder in einem Knoten und ruft gegbenenfals eine Methode zum balancieren auf.
	 */
	void checkSize() {
		if (children.size() < a)
			fusion();
		if (children.size() > b)
			split();
	}

	/**
	 * Macht aus einem Knoten mit sechs Kindern zwei mit jeweils drei Kindern.
	 */
	void split() 
	{
		// Hier muss unterschieden werden, ob man einen neuen RootKnoten braucht, weil der alte zu viele Kinder hat.
		if (this.getClass() == ABTreeRootNode.class)
		{
			this.insert(-1);
		} 
		else if (this.getClass() == ABTreeInnerNode.class)
		{
			// Neue InnerNode erstellen, da durch Split eine hinzukommen muss.
			ABTreeInnerNode newRoot = new ABTreeInnerNode(this.parent);
			
			// Drei Elemente aus dem alten Knoten in den neuen verschieben.
			for (int a = 0; a < 3; a++)
			{
				this.children.get(0).parent = newRoot;
				newRoot.children.add(this.children.get(0));
				this.children.remove(this.children.get(0));
			}
			
			// Neuen Knoten an die richtige Stelle einfügen.
			int m = 0;
			while (newRoot.getLowestKey() >= this.parent.children.get(m).getLowestKey()) m += 1;
			this.parent.children.add(m, newRoot);
			
			// Da durch den split der Vaterknoten nun mehr als 5 Knoten haben kann. Dies überprüfen.
			this.parent.checkSize();
		}
		
	}

	/**
	 * Enfernt den Knoten mit nur einem Kind und fügt das Kind einem Geschwisterknoten hinzu.
	 */
	void fusion() {		
		
		// Ermitteln mit welchem Geschwisterknoten der Knoten fusionieren muss.
		int m = 0;
		if (this.parent.children.size() > 2)
			while (this.getLowestKey() >= this.parent.children.get(m).getLowestKey()) m+=1;
		else
			m = ((ABTreeInnerNode)this.parent.children.get(0)).children.size() 
					> ((ABTreeInnerNode)this.parent.children.get(1)).children.size() ? 0 : 1;
		
		
		// Den neuen Knoten, in den Fusioniert werden soll, zwischenspeichern.
		ABTreeInnerNode newRoot = (ABTreeInnerNode) this.parent.children.get(m);
		
		// Das eine Kind in dem altem Knoten den neuen Parent hinzufügen.
		this.children.get(0).parent = newRoot;
		// Dem neuen Root das neune Kind hinzufügen.
		newRoot.children.add(0, this.children.get(0));
		// Den alten Knoten mit nur einem Kind entfernen.
		this.parent.children.remove(this);
		// Die neue Collection sortieren.
		Collections.sort(newRoot.children);
		//Da es sein kann, dass durch das hinzufügen eines Kindes beim Geschwisterknoten, es nun mehr als fünf hat. 
		newRoot.checkSize();
	}

	/**
	 * Schreibt den Inhalt des aktuellen Knoten auf die Console.
	 */
	void print() {
		System.out.print("(");
		for (int i = 0; i < children.size(); ++i)
			children.get(i).print();
		System.out.print(")");
	}
}
